# -*- coding: utf-8 -*-
"""
@Time ： 2023/4/5 22:00
@Auth ： 叶东宇
@File ：移除元素.py
"""

"""
采用一个尾指针right指向lis的最后，
从lis头部开始找，
每找一次 left+1
每找到一个target，调换right 和 left位置的数值，并且right - 1 
注意，当right - 1 时，如果碰到target，依然要让right-1

问题是何时让遍历停止
一开始我给出的条件是 left == target
但是我用的是for循环
并且在内部判断 left == target
这样会出现一种情况（每遍历一次，left + 1 , right - 1 , 并且我判断是否循环的条件在这两个语句前面）
那么会不会出现left + 1 = right
此时找到了target，这样left + 1, right - 1
这样就完美的 使 left > right(一开始我在程序最后并没有写return lis)，从而返回不了lis

出错了：dele3是正确的

"""
def dele(lis, target):
    """
    出错了，假设lis后面几个全是target
    我只进行了一次将right-1
    但是很有可能此时lis[right] == lis[left] = target
    这时候调换无意义
    出错的原因是因为在做之前没有思考的很完善
    :param lis:
    :param target:
    :return:
    """
    right = len(lis) - 1
    left = 0
    tag = 0
    for i in range(len(lis)):
        if lis[right] == target:
            tag += 1
            right -= 1
        if left >= right:
            print("len+ ", len(lis) - tag)
            return lis
        if lis[left] == target:
            tag += 1
            tmp = lis[left]
            lis[left] = lis[right]
            lis[right] = tmp
            right -= 1
        left += 1


def dele2(lis, target):
    """
    这个也错了，循环条件错了
    因为当lis=[1] target=1时
    left == right
    但是并没有元素被删除
    :param lis:
    :param target:
    :return:
    """
    right = len(lis) - 1
    left = 0
    tag = 0
    while left < right:
        if lis[right] == target:
            tag += 1
            right -= 1
            continue
        if lis[left] == target:
            tag += 1
            tmp = lis[left]
            lis[left] = lis[right]
            lis[right] = tmp
            right -= 1
        left += 1

    return len(lis) - tag, lis[:len(lis) - tag]


def dele3(lis, target):
    """
    这个也错了
    因为当lis=[1] target=1时
    left == right
    但是并没有元素被删除
    :param lis:
    :param target:
    :return:
    """
    right = len(lis) - 1
    left = 0
    tag = 0
    while left <= right:
        if lis[right] == target:
            tag += 1
            right -= 1
            continue
        if lis[left] == target:
            tag += 1
            tmp = lis[left]
            lis[left] = lis[right]
            lis[right] = tmp
            right -= 1
        left += 1

    return len(lis) - tag, lis[:len(lis) - tag]

if __name__ == "__main__":
    # lis = [1,2,3,4,5,6,7,3]
    lis = [1,2,3,3,4,5,3]
    target = 3
    print(dele3(lis, target))
